﻿namespace _6.图;

public class Solution
{
    public bool CanFinish(int numCourses, int[][] prerequisites)
    {
        //入度集合
        var inList = new int[numCourses];
        //入度为0的 点索引队列
        var queue = new Queue<int>(numCourses);

        //计算入度
        for (int i = 0; i < prerequisites.Length; i++)
        {
            var ship = prerequisites[i];
            //自己指向自己不可以
            if (ship[0] == ship[1])
                return false;
            //索引0入度边
            inList[ship[0]]++;
        }

        //将所有入读为0加入队列
        for (int i = 0; i<numCourses;  i++)
        {
            if (inList[i] == 0)
                queue.Enqueue(i);
        }

        //如果所有的的入读均不为0则说明一定存在环
        if(queue.Count == 0)
        {
            return false;
        }

        var topoResults = new List<int>(numCourses);
        while (queue.Count!=0)
        {
            var item = queue.Dequeue();
            topoResults.Add(item);
            //减少出度边顶点的入度
            for (int i = 0; i < prerequisites.Length; i++)
            {
                var ship = prerequisites[i];
                var j = ship[0];
                //这个节点相邻的点的入度-1
                if (item == ship[1])
                {
                    if (--inList[j] == 0)
                        queue.Enqueue(j);
                }
         
            }
        }

        return topoResults
            .Intersect(Enumerable.Range(0,numCourses))
            .Count() == numCourses;
    }
}


public class Solution2
{
    public int[] FindOrder(int numCourses, int[][] prerequisites)
    {
        //入度集合
        var inList = new int[numCourses];
        //入度为0的 点索引队列
        var queue = new Queue<int>(numCourses);

        //计算入度
        for (int i = 0; i < prerequisites.Length; i++)
        {
            var ship = prerequisites[i];
            //自己指向自己不可以
            if (ship[0] == ship[1])
                return [];
            //索引0入度边
            inList[ship[0]]++;
        }

        //将所有入读为0加入队列
        for (int i = 0; i < numCourses; i++)
        {
            if (inList[i] == 0)
                queue.Enqueue(i);
        }

        //如果所有的的入读均不为0则说明一定存在环
        if (queue.Count == 0)
        {
            return [];
        }

        var topoResults = new List<int>(numCourses);
        while (queue.Count != 0)
        {
            var item = queue.Dequeue();
            topoResults.Add(item);
            //减少出度边顶点的入度
            for (int i = 0; i < prerequisites.Length; i++)
            {
                var ship = prerequisites[i];
                var j = ship[0];
                //这个节点相邻的点的入度-1
                if (item == ship[1])
                {
                    if (--inList[j] == 0)
                        queue.Enqueue(j);
                }

            }
        }

        if(topoResults
            .Intersect(Enumerable.Range(0, numCourses))
            .Count() == numCourses)
        {
            return topoResults.ToArray();
        }

        return [];
    }
}


public class Solution3
{
    public IList<bool> CheckIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries)
    {

        //入度集合
        var inList = new int[numCourses];
        //入度为0的 点索引队列
        var queue = new Queue<int>(numCourses);

        //计算入度
        for (int i = 0; i < prerequisites.Length; i++)
        {
            var ship = prerequisites[i];
            //自己指向自己不可以，####由于题目ai != bi
            //if (ship[0] == ship[1])
            //    return [];
            //索引0入度边
            inList[ship[1]]++;
        }

        //将所有入读为0加入队列
        for (int i = 0; i < numCourses; i++)
        {
            if (inList[i] == 0)
                queue.Enqueue(i);
        }

        //如果所有的的入读均不为0则说明一定存在环，###由于题目没有环
        //if (queue.Count == 0)
        //{
        //    return [];
        //}

        var topoResults = new List<int>(numCourses);
        while (queue.Count != 0)
        {
            var item = queue.Dequeue();
            topoResults.Add(item);
            //减少出度边顶点的入度
            for (int i = 0; i < prerequisites.Length; i++)
            {
                var ship = prerequisites[i];
                var j = ship[1];
                //这个节点相邻的点的入度-1
                if (item == ship[0])
                {
                    if (--inList[j] == 0)
                        queue.Enqueue(j);
                }

            }
        }

        //思路，算出所有拓扑序列，只要有一个不是前提就为false

        var result = new List<bool>(queries.Length);
        for (int i = 0; i < queries.Length; i++)
        {
            var query = queries[i];
            var a = topoResults.IndexOf(query[0]);
            var b = topoResults.IndexOf(query[1]);
            if (a==-1 || b==-1 || prerequisites.Length==0)
            {
                result.Add(false);
                continue;
            }
       
            result.Add(a<b);
        }


        return result;
    }
}